import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = {4,6,8,5,9};
        heapSort(array);
    }

    /**
     * 堆排序
     * @param array:待排序数组
     */
    public static void heapSort(int[] array){
        int temp = 0;

        // i表示非叶子节点个数
        for(int i = array.length / 2 - 1; i >= 0; i--){
            adjustSort(array,i,array.length); // [9, 6, 8, 5, 4]
        }

        for(int j = array.length - 1; j > 0; j--){
            temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            adjustSort(array,0,j);
        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * 将非叶子节点的树调整为大顶堆
     * @param array:需要调整的数组
     * @param i:非叶子节点
     * @param length:表示对多少个元素进行调整
     */
    public static void adjustSort(int[] array, int i, int length){
        int temp = array[i];

        //调整
        for(int k = i * 2 + 1; k < length; k = k * 2 + 1){
            //当左子节点小于右子节点时，k++,即指向右子节点
            if(k + 1 < length && array[k] < array[k + 1]){
                k++;
            }

            //当右子节点大于前一个非叶子节点时，将两者调换位置
            if(array[k] > temp){
                array[i] = array[k];
                i = k;
            }else{
                break;
            }
        }
        //循环结束时，将i对应的父节点最大值放在堆顶
        array[i] = temp;
    }
}
